public class _01 {
    // https://leetcode.cn/problems/ones-and-zeroes/submissions/
    class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            // dp[i] : 从前i个元素中选取若干个元素，他们的0 1 个数小于m n 的子集最大长度
            // dp[i][j][k]  = dp[i-1][j][k]     dp[i-1][j-j0][k-k0] + 1;
            int length = strs.length;
            int [][] len = new int[length + 1][2];
            for(int i = 0 ; i < length ; i ++)
            {
                int n1 = strs[i].length();
                int m1 = 0 ;
                int n2 = 0 ;
                for(int j = 0 ; j < n1 ; j ++)
                {
                    if(strs[i].charAt(j) == '0') m1 ++;
                    else
                        n2++;
                }
                len[i+1][0] = m1;
                len[i+1][1] = n2;

            }
            int [][][] dp = new int[length + 1][m+1][n+1];
            for(int i = 1; i <= length ; i ++)
            {
                for(int j = 0 ; j <= m ; j ++)
                {
                    for(int k = 0; k <= n ; k ++)
                    {
                        dp[i][j][k] = dp[i-1][j][k];
                        if(len[i][0] <= j && len[i][1] <= k)
                        {
                            dp[i][j][k] = Math.max(dp[i][j][k],dp[i-1][j-len[i][0]][k-len[i][1]]+1);
                        }
                    }
                }
            }

            return dp[length][m][n];

        }


    }
}
